package simpledb.index;

import simpledb.common.DbException;
import simpledb.common.Permissions;
import simpledb.storage.Field;
import simpledb.storage.Page;
import simpledb.storage.PageId;
import simpledb.transaction.TransactionAbortedException;
import simpledb.transaction.TransactionId;

import java.io.IOException;
import java.util.Iterator;
import java.util.Map;

/**
 * BTreeChecker 是用于检查 B+ 树结构完整性（树的一致性）的辅助类。
 *
 * 主要功能包括：
 * - 检查父节点指针是否正确；
 * - 检查兄弟页面指针是否一致；
 * - 检查键值范围是否满足不变式；
 * - 检查记录到页面的指针是否有效；
 * - 可选地检查页面占用情况（如最小填充率）；
 */
public class BTreeChecker {

    /**
     * SubtreeSummary 类用于在递归检查过程中汇总子树的信息。
     * 它主要用于确保每个子树的结构一致性。
     */
    static class SubtreeSummary {
        public int         depth;      // 当前子树深度
        public BTreePageId ptrLeft;    // 左边相邻页面 ID
        public BTreePageId leftmostId; // 最左侧叶子页面 ID
        public BTreePageId ptrRight;   // 右边相邻页面 ID
        public BTreePageId rightmostId; // 最右侧叶子页面 ID

        SubtreeSummary() {
        }

        /**
         * 构造函数，基于一个叶子页面初始化摘要信息。
         */
        SubtreeSummary(BTreeLeafPage base, int depth) {
            this.depth = depth;

            this.leftmostId = base.getId();
            this.rightmostId = base.getId();

            this.ptrLeft = base.getLeftSiblingId();
            this.ptrRight = base.getRightSiblingId();
        }

        /**
         * 合并两个 SubtreeSummary 对象，验证它们的左右连接关系是否一致。
         * @param accleft 已有子树摘要
         * @param right 新子树摘要
         * @return 合并后的摘要
         */
        static SubtreeSummary checkAndMerge(SubtreeSummary accleft, SubtreeSummary right) {
            assert (accleft.depth == right.depth);
            assert (accleft.ptrRight.equals(right.leftmostId)); // 左子树的右指针应等于右子树的左指针
            assert (accleft.rightmostId.equals(right.ptrLeft));

            SubtreeSummary ans = new SubtreeSummary();
            ans.depth = accleft.depth;

            ans.ptrLeft = accleft.ptrLeft;
            ans.leftmostId = accleft.leftmostId;

            ans.ptrRight = right.ptrRight;
            ans.rightmostId = right.rightmostId;
            return ans;
        }
    }

    /**
     * 检查整个 B+ 树结构的一致性。
     *
     * 检查内容包括：
     * 1. 父节点指针是否正确；
     * 2. 兄弟节点指针是否一致；
     * 3. 键值范围是否符合不变式；
     * 4. 记录到页面的指针是否有效；
     * 5. 页面填充情况（如果启用）；
     *
     * @param bt 被检查的 B+ 树文件
     * @param tid 事务ID
     * @param dirtypages 脏页缓存
     * @param checkOccupancy 是否检查页面占用情况
     * @throws DbException 数据库异常
     * @throws IOException IO异常
     * @throws TransactionAbortedException 事务中断异常
     */
    public static void checkRep(BTreeFile bt, TransactionId tid, Map<PageId, Page> dirtypages, boolean checkOccupancy)
                                                                                                                      throws DbException,
                                                                                                                      IOException,
                                                                                                                      TransactionAbortedException {

        // 获取根指针页面
        BTreeRootPtrPage rtptr = bt.getRootPtrPage(tid, dirtypages);

        if (rtptr.getRootId() == null) {
            // 如果没有设置根页面，这是一个合法状态（空树）
            return;
        }

        // 从根节点开始递归检查整个树结构
        SubtreeSummary res = checkSubTree(bt, tid, dirtypages, rtptr.getRootId(), null, null, rtptr.getId(),
            checkOccupancy, 0);

        // 根节点不应有左右兄弟
        assert (res.ptrLeft == null);
        assert (res.ptrRight == null);
    }

    /**
     * 递归检查某个子树的结构一致性。
     *
     * @param bt B+ 树文件
     * @param tid 事务ID
     * @param dirtypages 脏页缓存
     * @param pageId 当前页面ID
     * @param lowerBound 当前子树中键值的下界
     * @param upperBound 当前子树中键值的上界
     * @param parentId 父页面ID
     * @param checkOccupancy 是否检查页面填充率
     * @param depth 当前子树的深度
     * @return 子树摘要信息
     * @throws TransactionAbortedException 事务中断异常
     * @throws DbException 数据库异常
     */
    static SubtreeSummary checkSubTree(BTreeFile bt, TransactionId tid, Map<PageId, Page> dirtypages,
                                       BTreePageId pageId, Field lowerBound, Field upperBound, BTreePageId parentId,
                                       boolean checkOccupancy, int depth) throws TransactionAbortedException,
                                                                         DbException {

        // 获取当前页面
        BTreePage page = (BTreePage) bt.getPage(tid, dirtypages, pageId, Permissions.READ_ONLY);

        // 验证该页面的父页面是否正确
        assert (page.getParentId().equals(parentId));

        // 如果是叶子节点
        if (page.getId().pgcateg() == BTreePageId.LEAF) {
            BTreeLeafPage bpage = (BTreeLeafPage) page;
            // 检查叶子页面的完整性（键值范围、兄弟指针、记录顺序等）
            bpage.checkRep(bt.keyField(), lowerBound, upperBound, checkOccupancy, depth);
            return new SubtreeSummary(bpage, depth);
        }
        // 如果是内部节点
        else if (page.getId().pgcateg() == BTreePageId.INTERNAL) {
            BTreeInternalPage ipage = (BTreeInternalPage) page;
            // 检查内部页面的完整性（键值范围、指针结构等）
            ipage.checkRep(lowerBound, upperBound, checkOccupancy, depth);

            SubtreeSummary acc = null;
            BTreeEntry prev = null;
            Iterator<BTreeEntry> it = ipage.iterator();

            // 处理第一个入口项
            if (it.hasNext()) {
                prev = it.next();
                acc = checkSubTree(bt, tid, dirtypages, prev.getLeftChild(), lowerBound, prev.getKey(), ipage.getId(),
                    checkOccupancy, depth + 1);
                lowerBound = prev.getKey(); // 更新下界为当前键
            }

            assert (acc != null); // 至少有一个入口
            BTreeEntry curr = prev;

            // 依次处理其他入口项
            while (it.hasNext()) {
                curr = it.next();
                SubtreeSummary currentSubTreeResult = checkSubTree(bt, tid, dirtypages, curr.getLeftChild(),
                    lowerBound, curr.getKey(), ipage.getId(), checkOccupancy, depth + 1);
                acc = SubtreeSummary.checkAndMerge(acc, currentSubTreeResult);
                lowerBound = curr.getKey(); // 更新下界
            }

            // 处理最后一个右子树
            SubtreeSummary lastRight = checkSubTree(bt, tid, dirtypages, curr.getRightChild(), lowerBound, upperBound,
                ipage.getId(), checkOccupancy, depth + 1);
            acc = SubtreeSummary.checkAndMerge(acc, lastRight);

            return acc;
        } else {
            assert false; // 不允许存在其他类型的页面
            return null;
        }
    }
}
